﻿#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
	int deleteAndEarn(vector<int>& nums) {
		const int N = 10001;
		// 1. 预处理
		int arr[N] = { 0 };
		for (auto x : nums) arr[x] += x;
		// 2. 在 arr 数组上，做⼀次 “打家劫舍” 问题
		// 创建 dp 表
		vector<int> f(N);
		auto g = f;
		// 填表
		for(int i = 1; i < N; i++)
		{
			f[i] = g[i - 1] + arr[i];
			g[i] = max(f[i - 1], g[i - 1]);
		}
		// 返回结果
		return max(f[N - 1], g[N - 1]);
	}
};